package de.unibi.comet.util;

import java.util.Iterator;
import java.util.NoSuchElementException;

/** Space efficient implementation of an array of booleans. Binary operations
 *  are also supported. */
public class BitArray implements Comparable<BitArray>, Iterable<Boolean> {
	private long[] array;
	private int size;
	
	public BitArray(int size) {
		this.size=size;
		int n = size/64;
		if (size%64>0) ++n;
		array = new long[n];
	}
	
	/** Copy constructor. */
	public BitArray(BitArray ba) {
		this.size=ba.size;
		this.array=new long[ba.array.length];
		System.arraycopy(ba.array, 0, this.array, 0, ba.array.length);
	}
	
	public boolean get(int index) {
		if ((index<0) || (index>=size)) throw new IndexOutOfBoundsException();
		int n = index/64;
		int m = index%64;
		return ((array[n]>>>m)&1L)==1L?true:false;
	}
	
	public void set(int index, boolean value) {
		if ((index<0) || (index>=size)) throw new IndexOutOfBoundsException();
		int n = index/64;
		int m = index%64;
		if (value) {
			array[n]=array[n]|(1L<<m);
		} else {
			array[n]=array[n]&~(1L<<m);
		}
	}
	
	public int size() {return size;}

	public int compareTo(BitArray o) {
		if (o.size!=this.size) throw new IllegalArgumentException();
		for (int i=array.length-1; i>=0; --i) {
			if (array[i]<o.array[i]) return -1;
			if (array[i]>o.array[i]) return 1;
		}
		return 0;
	}

	private class BitArrayIterator implements Iterator<Boolean> {
		private int n;
		private long l;
		BitArrayIterator() {
			n=0;
			l=array[0];
		}
		public boolean hasNext() { return n<size; }
		public Boolean next() {
			if (n>=size) throw new NoSuchElementException();
			boolean result = ((l&1L)==1L);
			l=l>>>1;
			++n;
			if ((n%64==0)&&(n<size)) l=array[n/64];
			return result;
		}
		public void remove() { throw new UnsupportedOperationException(); }
	}
	
	public Iterator<Boolean> iterator() { return new BitArrayIterator(); }

	/** Shifts left by one position. */
	public void shiftLeft() {
		long carry=0;
		for (int i=0; i<array.length; ++i) {
			long newCarry=array[i]>>>63;
			array[i]=(array[i]<<1)|carry;
			carry=newCarry;
		}
		if (size%64>0) array[array.length-1]&=(1L<<(size%64))-1L;		
	}
	
	/** Shifts right by one position. */
	public void shiftRight() {
		long carry=0;
		for (int i=array.length-1; i>=0; --i) {
			long newCarry=(array[i]&1L)<<63;
			array[i]=(array[i]>>>1)|carry;
			carry=newCarry;
		}
	}
	
	public void and(BitArray ba) {
		if (ba.size!=size) throw new IllegalArgumentException("Must have same sizes.");
		for (int i=0; i<array.length; ++i) array[i]&=ba.array[i];
	}
	
	public void or(BitArray ba) {
		if (ba.size!=size) throw new IllegalArgumentException("Must have same sizes.");
		for (int i=0; i<array.length; ++i) array[i]|=ba.array[i];
	}
	
	public void invert() {
		for (int i=0; i<array.length; ++i) array[i]=~array[i];
		if (size%64>0) array[array.length-1]&=(1L<<(size%64))-1L;
	}
	
	public boolean allZero() {
		boolean result = true;
		for (int i=0; i<array.length; ++i) {
			if (array[i]!=0) {
				result = false;
				break;
			}
		}
		return result;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (this==obj) return true;
		if ((obj==null) || (obj.getClass()!=this.getClass())) return false;
		BitArray ba = (BitArray)obj;
		if (ba.size!=size) return false;
		for (int i=0; i<array.length; ++i) {
			if (ba.array[i]!=array[i]) return false;
		}
		return true;
	}

	@Override
	public int hashCode() {
		long result=0;
		for (long i : array) {
			result^=i;
		}
		int lower=(int)result;
		int upper=(int)(result>>>32);
		return lower^upper;
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("(");
		for (int i=size-1; i>=0; --i) {
			int m=i/64;
			int n=i%64;
			sb.append(((array[m]>>>n)&1L)==1L?'1':'0');
		}
		sb.append(")");
		return sb.toString();
	}
}
